Project background:
This project encapsulates my work in the University of Illinois Chicago department of Mathematics, Statistics, and Computer Science's Spring 2025 Directed Reading Program (DRP). I presented a version of this content in a short talk at the conclusion of the semester.
https://sites.google.com/uic.edu/drpatuic/home
I was mentored by Jennifer Vaccaro, and am deeply grateful for her continued support and mentorship in this program! DRP was co-organized by Yijia Chen, Nick Christo, Clay Mizgerd, and Michael Gintz.
Abstract:
Graph Convolutional Networks (GCNs) are a scalable and efficient machine learning approach to semi-supervised learning on graph structured data. GCNs are used to classify graphs and their features by aggregating information across adjacent nodes according to learnable parameters. They are a powerful tool which extends the concept of convolution on grid structured data (i.e. image processing contexts) to graph structured data. This finds applications in numerous settings including functional brain connectivity analysis, node classification, molecular property prediction, and link prediction.
I will discuss GCNs as first proposed by Thomas Kipf and Max Welling in their 2016 paper $\textit{Semi-Supervised Classification with Graph Convolutional Networks}$, in which the convolutional architecture they design emerges from a localized first-order approximation of spectral graph convolutions. This model learns hidden layer representations that encode information about local graph structutre and node features, enabling the model to learn complex features of the graph, and in turn enabling the various abilities of GCNs.
Primary Texts:
$\textit{Graph Representation Learning}$ - William L. Hamilton (2020)
$\textit{Semi-Supervised Classification with Graph Convolutional Networks}$ - Kipf & Welling (2017)
I will start with a slightly simpler type of model: the Convolutional Neural Network (CNN). Traditional CNNs operate over grid structured data such as image pixel matrices, and learn hidden layer representations that encode features of the input grid and enable the model's application in various tasks. These types of model have found widespread use in computer vision, though they have uses in any setting where the data can be structured as a euclidean grid.
Every image is a grid of nicely aranged pixels which each have some value $x_{i}$ associated with them. In the case of greyscale images, this is a single value between 0 and 1. In color images, $x_{i} = <r,g,b>$ is a vector encoding the red, green, and blue values.
The main component of convolution is the kernel, which is simply another (typically smaller) grid with a defined weight for each entry. In one convolutional step, the kernel is passed over the entire image as partially illustrated below.
from IPython.display import Image
Image(filename="Graphics/Grid convolution.png", width=750)
At each step as the kernel moves, a new value $x'_{i}$ is generated for each pixel by convolving the filter weights with the pixel values, which just means taking a weighted linear combination of each pixel's immediate neighbors:
Image(filename='Graphics/2 - kernel on grid .png', width=750)
Once the kernel has been passed across the entire image, the effect is that information is spread across pixels, based on the chosen weights. How the weights are chosen determines the effect of the convolution. This fact is demonstrated next.
Image(filename='Graphics/Image convolution.png', width=550)